#leetcode题目153：寻找旋转排序数组中的最小值
#难度：中等
#时间复杂度：O(logn)
#空间复杂度：O(1)
#方法：二分查找

#注意：是33题的拓展
#要求时间复杂度必须为O(logn)，所以也能看出来暗示是二分查找

from typing import List
class Solution:
    def findMin(self, nums: List[int]) -> int:
        """
        寻找旋转排序数组中的最小值
        已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。
        例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
        - 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
        - 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
        注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
        给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。
        请你找出并返回数组中的 最小元素 。
        """
        l = 0
        r = len(nums) - 1
        
        while l < r:
            mid = l + ((r - l) >> 1)  # 防止溢出，等同于 (l + r) // 2
            
            if nums[mid] <= nums[r]:
                # 如果中间元素小于等于右边界元素，说明最小值在左半部分（包括mid）
                r = mid
            else:
                # 如果中间元素大于右边界元素，说明最小值在右半部分（不包括mid）
                l = mid + 1
        
        return nums[l]


#测试数据
nums=[3,4,5,1,2]
#预期输出：1
solution=Solution()
print(solution.findMin(nums))

nums=[4,5,6,7,0,1,2]
#预期输出：0
solution=Solution()
print(solution.findMin(nums))

nums=[11,13,15,17]
#预期输出：11
solution=Solution()
print(solution.findMin(nums))